package leetcode_2501_2600;

import java.util.*;

public class LeeCode_2508 {
    public static void main(String[] args) {
        List<List<Integer>> list = new ArrayList<>();
        ArrayList<Integer> l1 = new ArrayList<>();
        ArrayList<Integer> l2 = new ArrayList<>();
        ArrayList<Integer> l3 = new ArrayList<>();
        l1.add(1);
        l1.add(2);
        l2.add(1);
        l2.add(3);
        l3.add(1);
        l3.add(4);
        list.add(l1);
        list.add(l2);
        list.add(l3);
        System.out.println(isPossible(4, list));
    }
    private static boolean isPossible(int n, List<List<Integer>> edges) {
        int[] du = new int[n + 1];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (List<Integer> edge : edges) {
            Integer x = edge.get(0);
            Integer y = edge.get(1);
            du[x]++;
            du[y]++;
            if (map.containsKey(x)){
                map.get(x).add(y);
            }else {
                Set<Integer> set = new HashSet<>();
                set.add(y);
                map.put(x, set);
            }
            if (map.containsKey(y)){
                map.get(y).add(x);
            }else {
                Set<Integer> set = new HashSet<>();
                set.add(x);
                map.put(y, set);
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (du[i] % 2 == 1){
                list.add(i);
            }
        }
        if (list.size() == 0)
            return true;
        if (list.size() == 2){
            Integer x = list.get(0);
            Integer y = list.get(1);
            if (!map.get(x).contains(y)) {
                return true;
            }
            for (int i = 1; i <= n; i++) {
                if (i != x && i != y){
                    if (!map.containsKey(i))
                        return true;
                    if (!map.get(i).contains(y) && !map.get(i).contains(x))
                        return true;
                }
            }
        }
        if (list.size() == 4){
            int a = list.get(0), b = list.get(1), c = list.get(2), d = list.get(3);
            return (!map.get(a).contains(b) && !map.get(c).contains(d)) ||
                    (!map.get(a).contains(c) && !map.get(b).contains(d)) ||
                    (!map.get(a).contains(d) && !map.get(b).contains(c));
        }
        return false;
    }
}
